Understanding Queue, Deque, and PriorityQueue in Java

Course: Core Java Training

Topic: Understanding Queue, Deque, and PriorityQueue

Course URL: Core Java Training Course

Demo URL: Register for a Course Demo

Website: JustAcademy

1. Introduction

The Java Collections Framework provides several data structures for storing and processing groups of objects. Queue, Deque, and PriorityQueue are important structures used to manage elements based on processing order, insertion position, or priority.

A Queue commonly follows First-In-First-Out (FIFO) processing. A Deque allows insertion and removal at both ends, making it useful as either a queue or a stack. A PriorityQueue retrieves elements according to natural ordering or a custom Comparator.

Learning Objectives

• Understand the Queue interface and FIFO processing.
• Learn Queue methods and their behavior.
• Understand the Deque interface and double-ended operations.
• Implement stack operations using Deque.
• Understand PriorityQueue and heap-based ordering.
• Use Comparators to customize element priorities.
• Compare performance, applications, and limitations.

2. Understanding the Queue Interface

The Queue interface belongs to the java.util package and extends the Collection interface. It represents a collection of elements waiting to be processed.

Many Queue implementations follow FIFO ordering, in which the element inserted first is removed first. However, this behavior depends on the implementation. PriorityQueue, for example, uses priority-based ordering rather than insertion order.

2.1 What Is FIFO?

FIFO stands for First-In-First-Out. The first element added to a FIFO queue is the first element removed.

Insertion: 10 → 20 → 30
Removal:   10 → 20 → 30

A real-world example is a line of customers waiting at a ticket counter. Normally, the customer who arrives first is served first.

2.2 Characteristics of Queue

• Stores elements waiting for processing.
• Supports insertion, removal, and inspection operations.
• Often follows FIFO ordering.
• May allow or reject null elements depending on the implementation.
• Can be implemented using LinkedList or ArrayDeque.
• PriorityQueue is another Queue implementation that uses priority-based ordering.

2.3 Important Queue Methods

2.4 Difference Between add() and offer()

Both methods insert elements into a queue. The main difference is their failure behavior. The add() method may throw an exception if insertion is unsuccessful, while offer() returns false when the queue cannot accept an element. This distinction is particularly useful for capacity-restricted queues.

2.5 Difference Between remove() and poll()

Both methods remove the head element. The remove() method throws an exception if the queue is empty, whereas poll() returns null. Use poll() when an empty queue is an expected situation.

2.6 Difference Between element() and peek()

Both methods inspect the head without removing it. The element() method throws an exception if the queue is empty, whereas peek() returns null.

3. Implementing Queue Using LinkedList

The LinkedList class implements both Queue and Deque. It can be used to insert elements at the end and remove elements from the beginning.

Example Program

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("Amit");
        queue.offer("Priya");
        queue.offer("Rahul");

        System.out.println("Queue: " + queue);
        System.out.println("Head: " + queue.peek());
        System.out.println("Removed: " + queue.poll());
        System.out.println("Remaining: " + queue);
    }
}

Expected Output

Queue: [Amit, Priya, Rahul]
Head: Amit
Removed: Amit
Remaining: [Priya, Rahul]

Explanation

1. A Queue of String elements is created.
2. The offer() method adds three names.
3. The peek() method displays the head without removing it.
4. The poll() method removes Amit, the first element.
5. The remaining queue contains Priya and Rahul.

4. Understanding the Deque Interface

Deque stands for Double-Ended Queue. It extends Queue and supports insertion and removal at both the front and rear of a collection.

A Deque can operate as a FIFO queue or a LIFO stack. Common implementations include ArrayDeque and LinkedList.

4.1 Characteristics of Deque

• Supports operations at both ends.
• Can function as a normal queue.
• Can function as a stack.
• ArrayDeque uses a resizable array.
• LinkedList uses linked nodes.
• ArrayDeque does not permit null elements.

4.2 Important Deque Methods

4.3 Implementing Deque Using ArrayDeque

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        deque.offerFirst(20);
        deque.offerFirst(10);
        deque.offerLast(30);
        deque.offerLast(40);

        System.out.println("Deque: " + deque);
        System.out.println("First: " + deque.peekFirst());
        System.out.println("Last: " + deque.peekLast());

        System.out.println("Removed first: " + deque.pollFirst());
        System.out.println("Removed last: " + deque.pollLast());

        System.out.println("Remaining: " + deque);
    }
}

Expected Output

Deque: [10, 20, 30, 40]
First: 10
Last: 40
Removed first: 10
Removed last: 40
Remaining: [20, 30]

4.4 Explanation

1. offerFirst(20) inserts 20 at the front.
2. offerFirst(10) inserts 10 before 20.
3. offerLast(30) and offerLast(40) append elements at the rear.
4. peekFirst() and peekLast() inspect both ends.
5. pollFirst() and pollLast() remove elements from opposite ends.

5. Using Deque as a Stack

A stack follows LIFO, meaning Last-In-First-Out. The last element inserted is the first element removed. Java's Deque interface provides convenient methods for implementing this behavior.

Example Program

import java.util.ArrayDeque;
import java.util.Deque;

public class StackUsingDeque {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();

        stack.push("Java");
        stack.push("Python");
        stack.push("JavaScript");

        System.out.println("Stack: " + stack);
        System.out.println("Top: " + stack.peek());
        System.out.println("Popped: " + stack.pop());
        System.out.println("After pop: " + stack);
    }
}

Expected Output

Stack: [JavaScript, Python, Java]
Top: JavaScript
Popped: JavaScript
After pop: [Python, Java]

The most recently pushed element is at the front and is removed first. The pop() method throws an exception if the deque is empty.

6. Understanding PriorityQueue

PriorityQueue is a class in the java.util package that implements Queue using a heap-based data structure. Elements are retrieved according to natural ordering or a custom Comparator rather than insertion order.

By default, the smallest element is at the head. For integers, this means the lowest number is removed first. For custom objects, an appropriate ordering must be defined.

6.1 Characteristics of PriorityQueue

• Implements the Queue interface.
• Uses a heap-based internal structure.
• Supports natural ordering or custom Comparator ordering.
• Allows duplicate elements.
• Does not allow null elements.
• Does not guarantee sorted iteration.
• Is not synchronized for concurrent modifications.

6.2 Example: PriorityQueue of Integers

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        numbers.offer(40);
        numbers.offer(10);
        numbers.offer(30);
        numbers.offer(20);

        System.out.println("Head: " + numbers.peek());

        while (!numbers.isEmpty()) {
            System.out.println(numbers.poll());
        }
    }
}

Expected Output

Head: 10
10
20
30
40

6.3 Explanation

1. A PriorityQueue of integers is created.
2. Four numbers are inserted in a non-sorted order.
3. The peek() method returns the smallest element.
4. The poll() method removes the current head.
5. Repeated polling retrieves the values in ascending order.

Important: Printing a PriorityQueue directly does not guarantee sorted output. To retrieve elements in priority order, repeatedly use poll().

7. Custom Ordering with Comparator

A Comparator allows developers to customize the ordering of elements. For example, a PriorityQueue can retrieve the largest number first instead of the smallest number.

7.1 Maximum-First PriorityQueue

import java.util.Comparator;
import java.util.PriorityQueue;

public class MaxPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> numbers =
            new PriorityQueue<>(Comparator.reverseOrder());

        numbers.offer(25);
        numbers.offer(75);
        numbers.offer(10);
        numbers.offer(50);

        while (!numbers.isEmpty()) {
            System.out.println(numbers.poll());
        }
    }
}

Expected Output

75
50
25
10

The Comparator.reverseOrder() method reverses the natural ordering so the largest integer is retrieved first.

7.2 PriorityQueue with Custom Objects

Suppose a task management system must process tasks according to urgency. A smaller priority number represents a more urgent task.

import java.util.Comparator;
import java.util.PriorityQueue;

class Task {
    String name;
    int priority;

    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return name + " - Priority " + priority;
    }
}

public class TaskPriorityExample {
    public static void main(String[] args) {
        PriorityQueue<Task> tasks = new PriorityQueue<>(
            Comparator.comparingInt(task -> task.priority)
        );

        tasks.offer(new Task("Send Report", 3));
        tasks.offer(new Task("Fix Critical Bug", 1));
        tasks.offer(new Task("Update Documentation", 2));

        while (!tasks.isEmpty()) {
            System.out.println(tasks.poll());
        }
    }
}

Expected Output

Fix Critical Bug - Priority 1
Update Documentation - Priority 2
Send Report - Priority 3

The Comparator orders tasks by their priority field. Tasks with equal priorities are not guaranteed to be retrieved in insertion order. If stable ordering is required, include a sequence number as a secondary comparison key.

8. Difference Between Queue, Deque, and PriorityQueue

9. Time Complexity

The following table shows typical time complexity for ArrayDeque and PriorityQueue operations. Actual performance may depend on the implementation and the operation performed.

ArrayDeque offers efficient operations at both ends. PriorityQueue maintains a heap during insertion and removal, so these operations typically require logarithmic time.

10. Real-World Applications

10.1 Queue Applications

• Managing print jobs in arrival order.
• Processing customer service requests.
• Handling messages in sequential workflows.
• Implementing breadth-first search in graphs.

10.2 Deque Applications

• Implementing stack-based algorithms.
• Maintaining sliding-window calculations.
• Processing elements from either end of a sequence.
• Supporting algorithms that require efficient front and rear operations.

10.3 PriorityQueue Applications

• Scheduling tasks according to urgency.
• Finding shortest paths with Dijkstra's algorithm.
• Finding the smallest or largest K elements in a dataset.
• Processing events according to event time.
• Building Huffman coding algorithms.

11. Common Mistakes and Best Practices

11.1 Assuming Every Queue Uses FIFO

Queue ordering depends on its implementation. PriorityQueue retrieves elements according to priority, not insertion order.

11.2 Confusing peek() and poll()

peek() inspects the head without removing it. poll() removes and returns the head.

11.3 Expecting Sorted PriorityQueue Iteration

PriorityQueue iteration does not guarantee sorted order. Use repeated poll() calls to retrieve elements according to priority, or sort a separate array when a fully sorted collection is needed.

11.4 Inserting Null Elements

PriorityQueue and ArrayDeque reject null elements. Avoid null values in queues because they can also make empty-result handling more difficult in implementations that permit null.

11.5 Ignoring Thread Safety

ArrayDeque and PriorityQueue are not designed for unsynchronized concurrent modification. For concurrent producer-consumer applications, consider BlockingQueue, BlockingDeque, or PriorityBlockingQueue, depending on the requirements.

11.6 Choosing the Wrong Structure

• Choose Queue for elements waiting to be processed.
• Choose ArrayDeque for efficient operations at both ends or stack behavior.
• Choose PriorityQueue when the next element must be selected by priority.

12. Practice Exercises

1. Create a Queue of five student names and remove them one by one.
2. Check whether a Queue is empty before calling poll().
3. Create an ArrayDeque and insert elements at both ends.
4. Implement a stack of integers using Deque.
5. Create a PriorityQueue and retrieve numbers in ascending order.
6. Create a maximum-first PriorityQueue using Comparator.reverseOrder().
7. Create a Task class with a priority field and process tasks using a Comparator.
8. Compare the removal order of LinkedList-based Queue and PriorityQueue.

13. Mini Project: Task Processing System

Objective: Develop a task processing system that demonstrates normal queue processing and priority-based processing.

Requirements

• Store regular tasks in a Queue.
• Process regular tasks in FIFO order.
• Store urgent tasks in a PriorityQueue.
• Process urgent tasks according to a numeric priority.
• Display pending tasks and report when a queue is empty.

Implementation Steps

1. Create a Task class with a name and priority.
2. Use a Queue for regular tasks.
3. Use a PriorityQueue with a Comparator for urgent tasks.
4. Implement methods for adding and processing tasks.
5. Test the application with tasks inserted in different orders.
6. Verify that each data structure follows its configured ordering.

14. Interview Questions and Answers

Q1. What is Queue in Java?

Answer: Queue is an interface used to hold elements before processing. It provides methods such as offer(), poll(), and peek().

Q2. What is FIFO?

Answer: FIFO means First-In-First-Out, where the first element inserted is removed first.

Q3. What is the difference between poll() and remove()?

Answer: Both remove the head. If the queue is empty, poll() returns null, while remove() throws an exception.

Q4. What is Deque?

Answer: Deque is a double-ended queue that supports insertion and removal at both ends.

Q5. Can Deque be used as a stack?

Answer: Yes. The push(), pop(), and peek() methods support LIFO stack operations.

Q6. What is PriorityQueue?

Answer: PriorityQueue is a heap-based Queue implementation that retrieves elements according to natural ordering or a custom Comparator.

Q7. Does PriorityQueue preserve insertion order?

Answer: No. It retrieves elements according to priority, and elements with equal priority do not have a guaranteed order.

Q8. How do you retrieve the largest number first?

Answer: Create a PriorityQueue with Comparator.reverseOrder().

Q9. Can PriorityQueue contain null?

Answer: No. Attempting to insert null throws NullPointerException.

Q10. Is PriorityQueue thread-safe?

Answer: No. Use PriorityBlockingQueue when a thread-safe priority queue is required.

Q11. Why is ArrayDeque often preferred to Stack?

Answer: ArrayDeque provides efficient stack operations and is generally preferred for single-threaded stack usage over the legacy Stack class.

Q12. What is the insertion time complexity of PriorityQueue?

Answer: Insertion typically takes O(log n), retrieving the head takes O(1), and removing the head takes O(log n).

15. Quick Revision

• Queue: Holds elements waiting for processing.
• FIFO: First-In-First-Out.
• Deque: Supports operations at both ends.
• LIFO: Last-In-First-Out.
• ArrayDeque: Useful for queue and stack operations.
• PriorityQueue: Retrieves the element that comes first according to its ordering rule.
• offer(): Attempts insertion.
• poll(): Removes the head or returns null if empty.
• peek(): Inspects the head without removal.
• Comparator: Defines custom ordering.
• PriorityQueue iteration: Does not guarantee sorted order.
• Thread safety: Use concurrent alternatives when required.

16. Conclusion

Queue, Deque, and PriorityQueue are important Java data structures with different processing rules. Queue is useful for managing elements waiting for processing, Deque provides flexibility at both ends, and PriorityQueue retrieves elements according to a defined priority.

Understanding their methods, ordering rules, time complexity, and real-world applications helps developers select the appropriate data structure and write efficient Java programs. Practice the examples and exercises to build confidence in using these collections.

Recommended Learning Resources

Explore the Core Java Training Course to continue learning Java programming and Collections Framework concepts.

To learn more about course options, visit Register for a Course Demo.

Explore additional resources on the JustAcademy website.